//
//  extra.cpp
//  shunxubiao
//
//  Created by 刘文栖 on 2017/8/2.
//  Copyright © 2017年 刘文栖. All rights reserved.
//

#include "extra.hpp"

//创建链表
SeqList CreateList(int n){
    SeqList L;
    L.data=new int[n];
    int *num = L.data;
    int i;
    for (i=0; i<InitSize; i++) {
        printf("please input n: ");
        scanf("%d", num++);
    }
    L.length = i;
    return L;
}

void PrintList(SeqList L){
    printf("现在链表：");
    for (int i=0; i<L.length; i++) {
        printf("%d\n", L.data[i]);
    }
}

//从顺序表中删除具有最小值的元素，并返回该值，空出位置由最后一个元素填补
bool Del_Min(SeqList &L, int &value){
    if (L.length==0) return false;
    value=L.data[0];
    int pos=0;
    for (int i=1; i<L.length; i++) {
        printf("%d\n", L.data[i]);
        if (L.data[i]<value) {
            value=L.data[i];
            pos=i;
        }
    }
    L.data[pos] = L.data[L.length-1];
    L.length--;
    return true;
}

//设计算法，将顺序表内所有元素逆置，空间复杂度为O(1)
void Reverse(SeqList &L){
    int temp, i;
    for (i=0; i<L.length/2; i++) {
        temp = L.data[i];
        L.data[i]=L.data[L.length-1-i];
        L.data[L.length-1-i] = temp;
    }
}

//删除长度为n的线性表中值为x的数据元素，时间复杂度O(n)，空间复杂度O(1)
void Del_x_1(SeqList &L, int x, int n){
//    //一
//    int i,k=0;
//    for (i=0; i<n; i++) {
//        if (L.data[i] == x) {
//            k++;
//        } else {
//            L.data[i-k] = L.data[i];
//        }
//    }
//    L.length -=k;
    
    //二
    int k=0, i;
    for (i=0; i<L.length; i++) {
        if (L.data[i] != x) {
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
}

//从有序顺序表中删除值在s到t(s<t)之间的所有元素，s或t不合理或顺序表为空则显示错误并退出
bool Del_s_t(SeqList &L, int s, int t){
    if (s>=t || L.length == 0) return false;
    int i=0, j;
//    while (L.data[i] >= s) {
//        i++;
//    }
    for (; i<L.length && L.data[i] < s; i++);
    if (L.length == i) return false;
    for (j=i; j<L.length && L.data[j] <= t; j++);
    //k = j-i;
    for (; j<L.length; i++, j++) {
        L.data[i] = L.data[j];
    }
    L.length = i;
    return true;
}

//从顺序表中删除值在s和t(s<t)之间的所有元素，s或t不合理或者顺序表为空则显示错误并退出
bool Del_s_t2(SeqList &L, int s, int t){
    if (s>=t || L.length == 0) return false;
    int i=0, k=0;
    for (i=0; i<L.length; i++) {
        if (L.data[i] >= s && L.data[i] <= t) {
            k++;
        } else {
            L.data[i-k] = L.data[i];
        }
    }
    L.length -= k;
    return true;
}

//从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同
bool Del_Same(SeqList &L){
    if (L.length == 0) return false;
    int i,j;
    for (i=0, j=1; j<L.length; j++) {
        if (L.data[i] != L.data[j]) {
            L.data[++i] = L.data[j];
        }
    }
    L.length = i+1;
    return true;
}

//将两个有序顺序表合并成一个新的有序顺序表，由函数返回结果顺序表
SeqList Merge(SeqList &L, SeqList &M){
    SeqList N;
    N.MaxSize = 20;
    N.data = new int[10];
    int i=0, j=0, k=0;
    while (i<L.length && j<M.length) {
        if (L.data[i] < M.data[j]) {
            N.data[k] = L.data[i];
            i++;
        } else {
            N.data[k] = M.data[j];
            j++;
        }
        k++;
    }
    if (i == L.length) {
        for (; j<M.length; j++) {
            N.data[k++] = M.data[j];
        }
    }
    if (j == M.length) {
        for (; i<L.length; i++) {
            N.data[k++] = L.data[i];
        }
    }
    N.length = k;
    return N;
}

//在一维数组A[m+n]中存放两个线性表，将两个线性表位置互换
//交换指定两个位置之间的元素
void Reverse_List(SeqList &L, int left, int right){//
    int i, temp;
    int mid = (right - left)/2;
    for (i=0; i<=mid; i++) {
        temp = L.data[left+i];
        L.data[left+i] = L.data[right-i];
        L.data[right-i] = temp;
    }
}
//交换主逻辑
void Exchange(SeqList &L, int m, int n){
    Reverse_List(L, 0, m-1);
    Reverse_List(L, m, m+n-1);//注意是m+n-1，这里传递的是索引
    Reverse_List(L, 0, m+n-1);
}

//要求用最少的时间在有序顺序表中寻找值为x的元素，找到后和后继元素交换位置，找不到将其插入表中并使得表中元素仍然有序
void Select_Exchange_Insert(SeqList &L, int x){
    int low = 0,
    high = L.length - 1;
    int mid=0;
    while (low <= high) {
        mid = (low + high)/2;
        if (L.data[mid] == x) break;
        else if (L.data[mid] < x) low = mid+1;
        else high = mid-1;
    }
    if (L.data[mid] == x && mid != L.length - 1) {
        int t = L.data[mid+1];
        L.data[mid+1] = L.data[mid];
        L.data[mid] = t;
    }
    if (low > high) {
        for (int i=L.length-1; i>high; i--) {
            L.data[i+1] = L.data[i];
        }
        L.data[high+1] = x;
    }
}

//找出两个序列的中位数
int Search_M(SeqList &A, SeqList &B){
    int s1 = 0, d1 = A.length - 1, s2 = 0, d2 = B.length - 1;
    int m1=0, m2=0;
    while (s1 != d1 && s2 != d2) {
        m1 = (s1 + d1)/2;
        m2 = (s2 + d2)/2;
        if (A.data[m1] == B.data[m2]) {
            return A.data[m1];
        } else if (A.data[m1] < B.data[m2]){
            if ((s1 + d1) % 2 == 0) {
                s1 = m1;
                d2 = m2;
            } else {
                s1 = m1 + 1;
                d2 = m2;
            }
        } else {
            if ((s2 + d2) % 2 == 0) {
                d1 = m1;
                s2 = m2;
            } else {
                d1 = m1;
                s2 = m2 + 1;
            }
        }
    }
    return A.data[m1] < B.data[m2] ? A.data[m1] : B.data[m2];
}

//找出主元素，主元素个数大于总个数的一半，每个元素的大小范围是0<=ai<n
int Find_Majority(SeqList &L){
    if (L.length == 0) return -1;
    int c, i;
    int k=1;
    c = L.data[0];
    for (i=1; i<L.length; i++) {
        if (c == L.data[i]) {
            k++;
        } else if (k == 0) {
            c = L.data[i];
            k=1;
        } else {
            k--;
        }
    }
    if (k > 0) {//如果是主元素，k一定大于0，但是k>0不一定是主元素，需要加以校验
        k = 0;
        for (i=0; i<L.length; i++) {
            if (L.data[i] == c) {
                k++;
            }
        }
        if (k > L.length/2) {
            return c;
        }
    }
    return -1;
}





